Théorème fondamental : existence

Démonstration de l'existence de la décomposition en produit de facteurs premiers

On procède par récurrence forte. Pour $n⩾2$ , soit $P(n)$ la propriété : « l'entier $n$ s'écrit comme produit de facteurs premiers ».

Initialisation
Pour $n=2$ , on a $2=2$ , ce qui fournit une écriture de $2$ comme produit de facteurs premiers.
La propriété $P(2)$ est donc vraie.

Hérédité
On suppose qu'il existe un entier $n\in \mathbb{N}$ tel que $P(m)$ est vraie pour tout $m\in \{1;...;n\}$ .
Montrons que $P(n+1)$ est vraie, c'est-à-dire : « l'entier $n+1$ s'écrit comme produit de facteurs premiers ».

• Si $n+1$ est premier, alors on a $n+1=n+1$ , ce qui fournit une écriture de $n+1$ comme produit de facteurs premiers.
• Si $n+1$ n'est pas premier, alors il existe un nombre premier $p$ divisant $n+1$ .

On a donc $n+1=pq$ avec $q\in {\mathbb{N}}^{\ast }$ .
Comme $p⩾2$ , on a nécessairement $q\in \{2;...;n\}$ .
En effet, $q\ne 1$ sinon $n+1$ serait premier, et 
$q={\displaystyle \frac{n+1}{p}}⩽{\displaystyle \frac{n+1}{2}}⩽{\displaystyle \frac{n+n}{2}}=n$ .
Par hypothèse de récurrence, $q$ s'écrit comme produit de facteurs premiers, et donc $n+1=pq$ s'écrit aussi comme produit de facteurs premiers.

La propriété $P(n+1)$ est donc vraie.

Conclusion 
$P(n)$ est initialisée à $n=2$ et est héréditaire à partir du rang $3$ , donc elle est vraie pour tout entier $n⩾2$ .